1. Field of the Invention
The present invention relates to a router device and routing method for routing a packet via an IP (Internet Protocol) network by using cache entries in a cache memory corresponding to some of the routing entries in a routing table that includes routing information relating a destination IP address of the packet to a routing path such as next hop or adjacent router connected to the router device.
2. Description of the Related Art
Conventionally, there has been one method available for performing a routing processing by using the exclusive hardware in order to produce a high-speed router device. In the method, the router device has large routing tables, so that the exclusive hardware needs to be configured to be of a mass capacity in order to store all of the routing tables in its limited storage capacity, thereby becoming very expensive.
In relation to the above conventional method, such a configuration has been employed that software thereof holds all of the routing tables in order to produce not only a high-speed but also inexpensive router device. In the configuration, the router device caches routing entries of some of these routing tables that have a high usage frequency into the dedicated hardware. The routing tables of the software may be searched if information of interest cannot be obtained upon retrieval by the dedicated hardware.
The above conventional technologies, however, have the following problems. The above method of searching the routing tables is based on a characteristic of a longest prefix match principle (hereinafter referred to as “longest match”). In the longest match, it is necessary to employ a routing entry having a higher priority than the routing entries that have a plurality of matched conditions, that is, to employ such a routing entry so as to have a long network address mask.
There is available a CAM (Content-Addressable Memory) that can perform such a longest match and is provided with a three-valued retrieval capability. However, the CAM is expensive and has a small capacity, so that taking into account problems, to be solved, of a large power dissipation and a large mounting area on a board at the time of mounting. Accordingly, it becomes preferable to use hardware having an inexpensive and general-purpose full-match retrieval capability in order to construct a small and inexpensive device.
Further, if one routing entry present in the routing table is to be cached in a case where such a CAM is used, there occurs a possibility that routing may be performed mistakenly using this cached routing entry because those routing entries that have a higher priority than this cached routing entry are not cached.
To prevent this, it becomes necessary to simultaneously cache into the CAM all of the related routing entries having a higher priority than the cached routing entry. Consequently, the CAM cannot be used in a network having a larger number of routing tables than the number of the cache entries.
For example, in a router device provided with a default gateway and 100 routing entries, it becomes necessary to cache all of the 100 routing entries in order to cache the default gateway.
The routing table, therefore, is cached, in a popular manner, to a destination IP address of a processed packet, in which case, however, the cache entries are not masked. Therefore, if communication to a plurality of destination IP addresses routed using the same routing entry is cached, such an event may happen that the same number of cache entries as the number of these destination IP addresses are created.
In such a case, an originally small storage capacity of the dedicated hardware is decreased and, at the same time, a retrieval-hit ratio is not improved to thus increase a write frequency and decrease a cache-usage efficiency, thereby degrading a throughput.